// 位运算
// 位运算最关键的几个操作：
// 1.取最右边的 ‘1’：num &= (-num)
// 2.消除最右边的 ‘1‘：num &= (num - 1)
// 3.异或运算 ^：相同为 0（消消乐），不同为 1，无进位相加
// 4.位图的思想：如果题目中提出要求不适用额外的数据结构，那么大概率是要使用位图了
// 5.检查某一个 bit：(num >> x) & 1 == 1
// 6.设置某一个 bit：num |= (1 << x);

// 例题 5：
// 给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。
// 你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
//
//        以任意顺序返回这两个数字均可。
//
//        示例 1:
//
//        输入: [1]
//        输出: [2,3]
//        示例 2:
//
//        输入: [2,3]
//        输出: [1,4]
//        提示：
//
//        nums.length <= 30000

// 解题思路：
// 将 1 ~ N 的数字和 nums 中所有的数字都异或起来，得到的结果就是 a ^ b
// 再取 a ^ b 的最右边的位，根据这个位，将 1 ~ N 中的数字和 nums 中的所有元素分为 2 组
// a 和 b 就分别落在两组数中
// 将每组中的所有数字异或起来，就分别得到 a 和 b

public class MissingTwo {
    public int[] missingTwo(int[] nums) {
        int n = nums.length;
        int t = 0;
        for(int x : nums) t ^= x;
        for(int i = 1; i <= n + 2; i++) t ^= i;
        t &= (-t);

        int[] ret = new int[2];
        for(int x : nums){
            if((t & x) == 0) ret[0] ^= x;
            else ret[1] ^= x;
        }
        for(int i = 1; i <= n + 2; i++){
            if((t & i) == 0) ret[0] ^= i;
            else ret[1] ^= i;
        }
        return ret;
    }
}
